Public key cryptosystems use a pair of asymmetric related keys, one for encryption and the other for decryption. Encryption in this context does not necessarily imply that the result is confidential, since data encrypted with a private key can be decrypted by anyone holding the public key—which may be widely available. One of the key pair, the private key, is kept secret by the user, while the other key, the public key, can be publicly disclosed. The key pair must have the property that, given knowledge of the public key, it is infeasible to determine the private key.
A user receives or, with suitable hardware or software, can generate for itself a pair of keys which are generally two large numbers. The user keeps one of these keys private and never discloses it. The other can be safely made public, just like a phone number or similar personal data. Due to the way the keys are generated, information encrypted with the private key can only be decrypted with the public key and vice versa. Using a key pair means that the sender and receiver do not need to share a secret key.
Public keys do not have to be published to the world. They can be shared as widely or narrowly as business and privacy requirements dictate.
The term “user” is defined as any entity including individuals, groups of individuals, one or more individuals in a role, corporations, organisations, computer applications or systems, automated machines, etc.
Public key cryptography makes the following possible:                Anyone knowing the user's public key can send the user a message encrypted with that key and can be sure that only the user—who alone has the corresponding private key—can decrypt it. This provides confidentiality.        The user might also encrypt a message with his private key. This cannot provide confidentiality, because anyone who knows the corresponding public key can decrypt it. But the fact that they can decrypt it means the message must have come from the user—who alone has the private key. This provides authentication and can also be used as a basis for non-repudiation—the digital equivalent of a signature.        If a sender signs a message with his own private key and then encrypts it with the recipient's public key, confidentiality, authentication and non-repudiation are provided together.        
In practice, things are actually more complex. In the first situation, for performance and operational reasons, the sender will choose a random symmetric session key and a symmetric cipher to encrypt the message. The public key will be used to encrypt just the session key.
In the second situation above, a message is signed with a private key and this is known as a digital signature. One problem with signature methods is that cryptography can be slow due to the processing and communications overheads required. The volume of data sent can be more than double the size of the original message.
Confidentiality may not be required and it may be desirable to be able to send signed plaintext messages. A method can be used that does not require the entire message to be encrypted and therefore reduces processing and communication overheads. This method is based on obtaining a “digest” of the message the user wishes to sign. One form of obtaining a message digest is a hash function. A hash function is a one-way function which maps an arbitrarily long piece of plain text into a comparatively small fixed-length bit string which is the message digest.
The hash function has the property that if the message is changed in anyway an entirely different value of message digest is produced by the hash function. It should also not be possible to generate two messages that have the same message digest. Given P (plaintext) it should be easy to compute H(P) (hash of the plaintext). Given H(P) it should be effectively impossible to find P (the original plaintext).
In the second situation, the hash function is used to generate a message digest from the content of the message to be signed. The message digest is then encrypted using the private key of a key pair to obtain the signature. The original plaintext message is transmitted together with the signature.
A recipient of the message uses the same hash function to obtain a digest of the plaintext message that has been received. The recipient also decrypts the signature using the public key of the key pair and obtains the message digest which was sent by the originator. The recipient compares the two digests and if they are the same, the signature is verified and the recipient is assured of the integrity and authenticity of the message.
For public key encryption to be effective, a user must keep his private key secret. For example, this could be done by a password-protected smart card. In a traditional public key infrastructure, the user also needs a certificate for his public key. This certificate tells those the user deals with that the public key really does identify the user. The public key certificate is issued by a reputable agency, such as a bank.
A problem arises if the user is dealing with a business associate who does not know the bank issuing the certificate certifying the public key of the user. The bank itself can have a public key certificate, issued by a suitable umbrella organisation. That umbrella organisation too can have a public key certificate. This can result in a chain of certificates leading to a point (referred to as the root) which the business associate does know. The hierarchical chains of certificates ultimately end with a master organisation at the top of the hierarchical tree which has a self-signed certificate. This means that the public key of the self-signed certificate must be obtained by means outside the public key infrastructure system. Such means outside the system must include a “witnessable event”, to initiate (or, in computing jargon, “bootstrap”) the electronic infrastructure.
A means by which users can obtain the public key certificates they need, and be sure that those certificates are valid, is known as a public key infrastructure (PKI). A traditional PKI includes a Registration Authority (RA) to approve the issue of public key certificates, a Certificate Authority (CA) to issue those certificates, and a Directory to store them.
An RA represents the organisation, processes, procedures and systems that approve, create, renew, suspend or revoke unique key pairs. The RA is responsible for ensuring the uniqueness of the key pair within its name space and—depending upon how the RA is implemented—validating that the recipient of key pair (a person, application, server, hardware device, or file) is authorised to perform the privileges associated with it. This privilege validation could alternatively be performed by a Certificate Authority (see below). The RA can be managed internally or outsourced through a growing number of service providers.
A CA represents the organisation, processes, procedures and systems that control the issuance, renewal, suspension and revocation of digital certificates based on public keys approved by the registration authority. It may also be responsible for maintaining and publishing a list of the user community through its underlying directory structure. Like the RA, the CA can be outsourced as a service, but many enterprises prefer to manage both the CA and RA services internally, integrating them with other related administration processes such as human resource management.
Known PKI systems include the SET (Secure Electronic Transactions) system for credit card transactions in which a PKI tree hierarchy has a master SET root at the top of the hierarchy which has a self-signed public key. A lower level of the hierarchy is the brand of credit card. A lower level still is the banks issuing the credit cards and the lowest level of the hierarchy is the consumer.
A consumer can obtain a root public key from his bank, for example by visiting a branch of the bank and obtaining the bank's root CD-ROM which includes the bank's self-signed digital certificate. The consumer trusts the authenticity of the root public key obtained from the bank. However, the consumer has no means of authenticating a public key of any other node of the tree hierarchy.
The only “global” root public key available in the hierarchy that can authenticate all the other nodes in the tree hierarchy is that of the master SET root. If the public key is obtained for the master SET root by the consumer, the consumer can obtain certificates certifying the public keys of all other nodes in the hierarchy.
Known PKI hierarchies of this nature have the disadvantage that the user may not trust the master global root. Trust in this context is defined as knowing the identity of a party and having a record of performance of the party. Such trust can be passed between parties, if a trusted party recommends another party.
It is an aim of the present invention to enable a user to choose a root from which to obtain a root public key from any node in a PKI and to enable the user to use the root public key as a global root key to obtain a chain of certificates along a path to any other node in the PKI. This enables the user to choose an entity for its global root which it trusts.